Introduction

Public-key encryption uses two keys - a public encryption key and a private decryption key. When Alice wants to communicate with Bob, she generates a pair of public-private keys and sends Bob her public key, while keeping the private key for herself. This key can then be used by Bob to encrypt any message and only Alice, who has the private key, can decrypt it. Similarly, Bob can generate his own key pair and send Alice his public key. She would then be able to encrypt any message and Bob, who has his own private key, is the only one who can decrypt them.

Interestingly, anyone can send private messages to Alice or Bob, since they can just post their public keys on the Internet. This is the great advantage of public-key encryption - the public key cannot be used to decrypt messages, only to encrypt them. Nevertheless, the public and the private key are linked - to decrypt a message encrypted with a specific public key, you need to use its corresponding private key. This notion can be formalised as follows.

A public-key encryption scheme consists  of three algorithms: 

- $\textit{Gen}$ is a probabilistic key-generation algorithm which outputs a pair of keys $(k_e, k_d)$ with lengths $(n_e, n_d)$, respectively.
- $\textit{Enc}$ is an encryption algorithm which takes an encryption key $k_e$ and a message $m \in \{0,1\}^{l}$ and outputs a ciphertext $c = \textit{Enc}(k_e, m)$.
- $\textit{Dec}$ is a decryption algorithm which takes a decryption mey $k_d$ and a ciphertext $c \in \{0,1\}^{C}$ and outputs a plaintext $m = \textit{Dec}(k_d, c)$.

To be a *valid* public-key encryption scheme, the three algorithms must satisfy the following correctness property - for every message $m \in \mathcal{M}$ and $(k_e, k_d) \leftarrow \textit{Gen}()$:

$$\Pr_{(k_e, k_d) \leftarrow \textit{Gen}()}[\textit{Dec}(k_d, \textit{Enc}(k_e,m)) = m] \gt 1 - \textit{negl}()$$
Copy

The key-generation algorithm $\textit{Gen}$ is a probabilistic algorithm which generates public-private key pairs that can be used for encryption and decryption. The encryption function $\textit{Enc}$ takes a *public* key and encrypts messages with it, while the decryption algorithm $\textit{Dec}$ takes a *private* key and decrypts ciphertexts. 

The encryption scheme is considered valid, if for any public-private key pair $(k_e, k_d)$, generated by $\textit{Gen}$, and any message $m$, decrypting the ciphertext $c \coloneqq \textit{Enc}(k_e, m)$ with the key $k_d$ should result in the original plaintext $m$ with almost 100% certainty.
Copy

As with private-key encryption schemes, the message space is denoted by , and the ciphertext space is . However, there are two key spaces when using public-key encryption - denotes the public-key space, and denotes the private-key space.

It turns out that any reasonable definition of security for public-key encryption requires a probabilistic encryption function and key-generation algorithm and so decryption is allowed to fail with negligible probability - for example, when a prime number is needed but returns a composite.